package com.leetcode.题库;

import com.leetcode.common.model.TreeNode;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 覃国强
 * @date 2022-04-12 20:05
 */
public class 题库_0106_从中序与后序遍历序列构造二叉树 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] inorder =   {9, 3,  15, 20, 7};
    int[] postorder = {9, 15, 7,  20, 3};
    TreeNode node = solution.buildTree(inorder, postorder);

    PrintSolution printSolution = new PrintSolution();
    printSolution.printPreorder(inorder, postorder);
  }

  static
  class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
      Map<Integer, Integer> inorderValueMap = new HashMap<>();
      for (int i = 0; i < inorder.length; ++i) {
        inorderValueMap.put(inorder[i], i);
      }
      return helper(postorder, postorder.length - 1, inorderValueMap, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] postorder, int fatherIndex, Map<Integer, Integer> inorderValueMap, int leftBound, int rightBound) {
      if (leftBound > rightBound) {
        return null;
      }
      int value = postorder[fatherIndex];
      TreeNode root = new TreeNode(value);
      Integer inorderIndex = inorderValueMap.get(value);
      int leftFatherIndex = fatherIndex - (rightBound - inorderIndex) - 1;
      int rightFatherIndex = fatherIndex - 1;
      root.left = helper(postorder, leftFatherIndex, inorderValueMap, leftBound, inorderIndex - 1);
      root.right = helper(postorder, rightFatherIndex, inorderValueMap, inorderIndex + 1, rightBound);
      return root;
    }
  }

  static class PrintSolution {

    public void printPreorder(int[] inorder, int[] postorder) {
      Map<Integer, Integer> inorderValueMap = new HashMap<>();
      for (int i = 0; i < inorder.length; ++i) {
        inorderValueMap.put(inorder[i], i);
      }
      helper(postorder, postorder.length - 1, inorderValueMap, 0, inorder.length - 1);
    }

    private void helper(int[] postorder, int fatherIndex, Map<Integer, Integer> inorderValueMap, int leftBound, int rightBound) {
      if (leftBound > rightBound) {
        return;
      }
      int value = postorder[fatherIndex];
      Integer inorderIndex = inorderValueMap.get(value);
      int leftFatherIndex = fatherIndex - (rightBound - inorderIndex) - 1;
      int rightFatherIndex = fatherIndex - 1;
      System.out.print(value + " ");
      helper(postorder, leftFatherIndex, inorderValueMap, leftBound, inorderIndex - 1);
      helper(postorder, rightFatherIndex, inorderValueMap, inorderIndex + 1, rightBound);
    }
  }


}
